//	ID : pallab81
// 	PROG : 990
// 	LANG : C++
// 	2011-07-15-23.14.29 Friday
//
// 	"I have not failed, I have just found 10000 ways that won't work.
//


#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>

#include <cassert>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>

using namespace std;

#define fo(i,ed) for(int i = 0 ; i < ed ; ++i )
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define bip system("pause")
#define Int long long
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define mk make_pair
#define f first
#define s second
#define SET( ARRAY , VALUE ) memset( ARRAY , VALUE , sizeof(ARRAY) )

const int m_t = 2000; // maximum time
const int m_n = 40; // maximum tresure

int t,w;
int n;
int d[ m_n+10 ];
int v[ m_n+10 ];
int dp[ m_n ][ m_t ];
int mask;
string feed="";
inline void read() {
    scanf("%d",&n);
    fo(i,n) {
        scanf("%d %d",&d[i],&v[i]);
    }
}
inline int calc(int temp, int time) {
    return (time - (temp*3*w) );
}

inline int go(int indx, int now_time) {
    if( indx>n )return 0;
    int &best = dp[indx][now_time];
    if( best!=-1 )return best;

    if( calc( d[indx] , now_time) < 0 ) {
        best = go(indx+1,now_time);
    } else {
        int one = go(indx+1, now_time);
        int two = v[indx]+go(indx+1, calc(d[indx],now_time) );
        best = max(one,two);
    }

    return best;
}
inline void select(int &mask, int shift) {
    mask|= (1<<shift);
    return ;
}
inline bool is_select(int mask, int bit) {
    return (mask&(1<<bit))!=0 ;
}
inline void back_track(int indx, int now_time) {
    if(indx>n)return ;

    if(calc( d[indx], now_time)<0) {
        back_track(indx+1,now_time);
    } else {
        if( v[indx]+ go(indx+1,calc(d[indx],now_time)) > go(indx+1,now_time) ) {
            select(mask, indx);
            back_track(indx+1, calc(d[indx],now_time));
        } else {
            back_track(indx+1, now_time);
        }
    }
    return ;
}
inline void proc() {
    SET(dp,-1);
    int var = go(0,t);
    printf("%s%d\n",feed.c_str(),var);
    mask=0;
    back_track(0,t);
    int bit = __builtin_popcount( mask );
    printf("%d\n",bit);
    fo(i,n) {
        if(is_select(mask,i)) {
            printf("%d %d\n",d[i],v[i]);
        }
    }
    feed="\n";
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt","rt",stdin);
#endif
    while( scanf("%d %d",&t,&w)==2 ) {
        read();
        proc();
    }



    return 0;
}


